import java.util.*;

public class Test {
    // 题目1 ：打家劫舍Ⅲ
    public int rob(TreeNode root) {
        Map<TreeNode, Integer>map = new HashMap<>();
        return rob(root, map);
    }
    public int rob(TreeNode root, Map<TreeNode, Integer>map){
        if(root == null){
            return 0;
        }
        if(map.containsKey(root)){
            return map.get(root);
        }
        int maxVal = root.val;
        if(root.left != null){
            maxVal += rob(root.left.left, map) + rob(root.left.right, map);
        }
        if(root.right != null){
            maxVal += rob(root.right.left, map) + rob(root.right.right, map);
        }
        int ret = Math.max(maxVal, rob(root.left, map) + rob(root.right, map));
        map.put(root, ret);
        return ret;
    }

    // 方法二
    public int rob1(TreeNode root) {
        int[] ret = dsf(root);
        return ret[0] > ret[1] ? ret[0] : ret[1];
    }
    public int[] dsf(TreeNode root){
        if(root == null){
            return new int[2];
        }
        int[] ret = new int[2];
        int[] left = dsf(root.left);
        int[] right = dsf(root.right);
        ret[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        ret[1] = left[0] + right[0] + root.val;
        return ret;
    }

    // 题目2：打家劫舍Ⅳ
    public int minCapability(int[] nums, int k) {
        int left = 1;
        int right = 1;
        for(Integer x : nums){
            right = Math.max(right, x);
        }
        while(left < right){
            int mid = left + (right - left) / 2;
            if(calculate(nums, mid, k)){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
    public boolean calculate(int[]nums, int cap, int k){
        int f0 = 0, f1 = 0;
        for(Integer x : nums){
            if(x > cap){
                f0 = f1;
            }else{
                int temp = f1;
                f1 = Math.max(f0 + 1, f1);
                f0 = temp;
            }
        }
        return f1 >= k;
    }

    // 题目3：爱吃香蕉的珂珂
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 1;
        for(Integer x : piles){
            right = Math.max(right, x);
        }
        while(left < right){
            int mid = left + (right - left) / 2;
            if(calculate1(piles, mid, h)){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    }
    public boolean calculate1(int[]piles, int speed, int h){
        int sum = 0;
        for(Integer x : piles){
            sum += (x + speed - 1) / speed;
        }
        return sum > h;
    }

    // 题目4：修车的最少时间
    public long repairCars(int[] ranks, int cars) {
        long left = 1;
        long right = 101;
        for(Integer x : ranks){
            right = Math.min(right, x);
        }
        right = right * cars * cars;
        while(left < right){
            long mid = left + (right - left) / 2;
            if(calcu(ranks, mid, cars)){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
    public boolean calcu(int[] ranks, long minutes, int cars){
        long sum = 0;
        for(Integer x : ranks){
            sum += (int)Math.sqrt(minutes / x);
        }
        return sum >= cars;
    }

}
